package sort;

import java.util.Arrays;

/**
 * 描述:1.只能排序整数
 * 2.排序的数最好是范围较小，较为连续的一组
 * 3.速度比其他算法都快
 *
 * @author
 * @created 2022/1/4 20:35
 */
public class CountSort {

    public static void main(String[] args) {
        int[] arr = new int[]{5, 6, 67, 7, 87, 4, 3, 23, 45, 6, 7, 78, 6, 4, 43, 5, 6, 67, 67};
        countSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void countSort(int[] arr) {
        /*求出数组中最小和最大的值*/
        int max = arr[0];
        int min = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
            if (min > arr[i]) {
                min = arr[i];
            }
        }
        /*将下标表示那个值，值为下标为那个数字的数量*/
        int[] temp = new int[max - min + 1];
        for (int i = 0; i < arr.length; i++) {
            temp[arr[i] - min]++;
        }
        /*将数组拆分开来*/
        int begin = 0;
        for (int i = 0; i < temp.length; i++) {
            if (temp[i] != 0) {
                for (int j = 0; j < temp[i]; j++) {
                    arr[begin++] = min + i;
                }
            }
        }
    }
}
